package com.liufei.class03;

import com.liufei.class02.Code03_Comp;

import java.util.Arrays;

public class Code03_BSNearRight {

    /**
     * 有序数组中找到<=target最右的位置
     *
     * @param nums
     * @param target
     */
    public static int binarySearchNearRight(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int L = 0;
        int R = nums.length - 1;
        int ans = -1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (nums[mid] <= target) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return ans;
    }


    public static int nearRight(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        // 从左遍历
        /*int ans = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= target) {
                ans = i;
            } else {
                break;
            }
        }
        return ans;*/
        // 从右遍历，都一个就是
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] <= target) {
                return i;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        int maxLen = 1000;
        int maxValue = 1000;
        int times = 10000;
        boolean succeed = true;
        for (int i = 0; i < times; i++) {
            int[] nums = Code03_Comp.lenRandomValueRandom(maxLen, maxValue);
            Arrays.sort(nums);
            int target = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            int index1 = binarySearchNearRight(nums, target);
            int index2 = nearRight(nums, target);
            if (index1 != index2) {
                System.out.println("nums: " + Arrays.toString(nums));
                System.out.println("target: " + target);
                System.out.println("二分法的结果：" + index1);
                System.out.println("正常查找的结果：" + index2);
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "success" : "failed");
    }
}
